{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Matrix Block Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #matrix #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #矩阵 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: matrixBlockSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵区域和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m x n</code> 的矩阵 <code>mat</code> 和一个整数 <code>k</code> ，请你返回一个矩阵 <code>answer</code> ，其中每个 <code>answer[i][j]</code> 是所有满足下述条件的元素 <code>mat[r][c]</code> 的和： </p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>i - k <= r <= i + k, </code></li>\n",
    "\t<li><code>j - k <= c <= j + k</code> 且</li>\n",
    "\t<li><code>(r, c)</code> 在矩阵内。</li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1\n",
    "<strong>输出：</strong>[[12,21,16],[27,45,33],[24,39,28]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2\n",
    "<strong>输出：</strong>[[45,45,45],[45,45,45],[45,45,45]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>1 <= m, n, k <= 100</code></li>\n",
    "\t<li><code>1 <= mat[i][j] <= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [matrix-block-sum](https://leetcode.cn/problems/matrix-block-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [matrix-block-sum](https://leetcode.cn/problems/matrix-block-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,3],[4,5,6],[7,8,9]]\\n1', '[[1,2,3],[4,5,6],[7,8,9]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        i_max = len(mat)\n",
    "        j_max = len(mat[0])\n",
    "        res = [[-1]*j_max for _ in range(i_max)]\n",
    "        for i in range(i_max):\n",
    "            for j in range(j_max):\n",
    "                l_i = max(i-k,0)\n",
    "                r_i = min(i+k,i_max-1)\n",
    "                l_j = max(j-k,0)\n",
    "                r_j = min(j+k,j_max-1)\n",
    "                num = 0\n",
    "                for r in range(l_i,r_i+1):\n",
    "                    num = num + sum(mat[r][l_j:r_j+1])\n",
    "                res[i][j] = num\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        # 计算前缀和矩阵\n",
    "        prefix_sum = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                prefix_sum[i][j] = mat[i][j]\n",
    "                if i > 0:\n",
    "                    prefix_sum[i][j] += prefix_sum[i - 1][j]\n",
    "                if j > 0:\n",
    "                    prefix_sum[i][j] += prefix_sum[i][j - 1]\n",
    "                if i > 0 and j > 0:\n",
    "                    prefix_sum[i][j] -= prefix_sum[i - 1][j - 1]\n",
    "\n",
    "        new_matrix = [[0] * n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                r1, r2, c1, c2 = max(0, i - k), min(m - 1, i + k), max(0, j - k), min(n - 1, j + k)\n",
    "                sum_block = prefix_sum[r2][c2]\n",
    "                if r1 > 0:\n",
    "                    sum_block -= prefix_sum[r1 - 1][c2]\n",
    "                if c1 > 0:\n",
    "                    sum_block -= prefix_sum[r2][c1 - 1]\n",
    "                if r1 > 0 and c1 > 0:\n",
    "                    sum_block += prefix_sum[r1 - 1][c1 - 1]\n",
    "                new_matrix[i][j] = sum_block\n",
    "\n",
    "        return new_matrix"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        answer = []\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for r in range(m):\n",
    "            tmp = []\n",
    "            for c in range(n):\n",
    "                upper_r = min(m, r + k + 1)\n",
    "                lower_r = max(0, r - k)\n",
    "                upper_c = min(n, c + k + 1)\n",
    "                lower_c = max(0, c - k)\n",
    "                summ = 0\n",
    "                for i in range(lower_r, upper_r):\n",
    "                    for j in range(lower_c, upper_c):\n",
    "                        summ += mat[i][j]\n",
    "                tmp.append(summ)\n",
    "            answer.append(tmp)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        answer=[[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                t=self.valid(i,j,mat,k)\n",
    "                answer[i][j]=t\n",
    "        return answer\n",
    "\n",
    "\n",
    "\n",
    "    def valid(self,i,j,mat,k):\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        x_low=i-k\n",
    "        x_high=i+k+1\n",
    "        y_low=j-k\n",
    "        y_high=j+k+1\n",
    "        if x_low<0:\n",
    "            x_low=0\n",
    "        if x_high>=m:\n",
    "            x_high=m\n",
    "        if y_low<0:\n",
    "            y_low=0\n",
    "        if y_high>=n:\n",
    "            y_high=n\n",
    "        ans=0\n",
    "        for i in range(x_low,x_high):\n",
    "            ans+=sum(mat[i][y_low:y_high])\n",
    "        return ans\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        res = []\n",
    "        for i in range(0,m):\n",
    "            res.append([0] * n)\n",
    "        \n",
    "        for i in range(0,m):\n",
    "            for j in range(0,n):\n",
    "                result = 0\n",
    "                for temp_i in range(max(0,i-k), min(i+k, m-1)+1):\n",
    "                    for temp_j in range(max(0,j-k), min(j+k, n-1)+1):\n",
    "                        result += mat[temp_i][temp_j]\n",
    "                res[i][j] = result\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        r = len(mat)\n",
    "        c = len(mat[0])\n",
    "        result = [[0 for _ in range(c)] for _ in range(r)]\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                result[i][j] = self.get_sum(mat, i, j, k)\n",
    "                pass\n",
    "            pass\n",
    "        return result\n",
    "        pass\n",
    "\n",
    "    def get_sum(self, mat, i, j, k):\n",
    "        r = len(mat)\n",
    "        c = len(mat[0])\n",
    "\n",
    "        r_top = max(0,i-k)\n",
    "        r_down = min(r,i+k+1)\n",
    "        c_left = max(0,j-k)\n",
    "        c_right = min(c,j+k+1)\n",
    "        s = 0\n",
    "        for x in range(r_top,r_down) :\n",
    "            for y in range(c_left,c_right) :\n",
    "                s += mat[x][y]\n",
    "                pass\n",
    "            pass\n",
    "        return s\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        tot=[]\n",
    "        def check(x,y):\n",
    "            ans=0\n",
    "            a=min(m-1,x+k)\n",
    "            c=max(0,x-k)\n",
    "            b=min(n-1,y+k)\n",
    "            d=max(0,y-k)\n",
    "            for i in range(c,a+1):\n",
    "                for j in range(d,b+1):\n",
    "                    ans+=mat[i][j]\n",
    "            return ans\n",
    "            \n",
    "                   \n",
    "        for i in range(m):\n",
    "            tott=[]\n",
    "            for j in range(n):\n",
    "                tott.append(check(i,j))\n",
    "            tot.append(tott)\n",
    "        return tot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = 0\n",
    "                for h in range(max(0, i - k), min(m, i + k + 1)):\n",
    "                    for kk in range(max(0, j - k), min(n, j + k + 1)):\n",
    "                        ans[i][j] += mat[h][kk]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        answer = []\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        for r in range(len(mat)):\n",
    "            tmp = []\n",
    "            for c in range(len(mat[0])):\n",
    "                upper_r = min(m, r+k+1)\n",
    "                lower_r = max(0, r-k)\n",
    "                upper_c = min(n, c+k+1)\n",
    "                lower_c = max(0, c-k)\n",
    "                summ = 0\n",
    "                for i in range(lower_r, upper_r):\n",
    "                    for j in range(lower_c, upper_c):\n",
    "                        summ += mat[i][j]\n",
    "                tmp.append(summ)\n",
    "\n",
    "            answer.append(tmp)\n",
    "\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        row,col = len(mat),len(mat[0])\n",
    "        res = [[0]*col for _ in range(row)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                sums = 0\n",
    "                m_r,n_r = max(0,i-k),min(row-1,i+k)\n",
    "                m_c,n_c = max(0,j-k),min(col-1,j+k)\n",
    "                for m in range(m_r,n_r+1):\n",
    "                    sums += sum(mat[m][m_c:n_c+1])\n",
    "                res[i][j] = sums\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        #max(i - k, 0) <= r <= min(i + k,  n - 1) \n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        ans = [[0] * m for _ in range(n) ]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                ans[i][j] = sum(mat[r][c] for r in range(max(i - k, 0), min(i + k,  n - 1)+1 ) for c in  range(max(j - k, 0), min(j + k,  m - 1)+1 ))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        answer=[[0]*n for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums=0\n",
    "                for x in range(max(i-k,0),min(i+k+1,m)):\n",
    "                    for y in range(max(j-k,0),min(j+k+1,n)):\n",
    "                        sums+=mat[x][y]\n",
    "                answer[i][j]=sums\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                up, down = max(i - k, 0), min(i + k + 1, m)\n",
    "                left, right = max(j - k, 0), min(j + k + 1, n)\n",
    "                res[i][j] = sum([sum(row[left:right]) for row in mat[up:down]])\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def check(r, c):\n",
    "            ans = 0\n",
    "            for i in range(max(0, (r - k)), min((r + k + 1), R)):\n",
    "                for j in range(max(0, (c - k)), min((c + k + 1), C)):\n",
    "                    ans += mat[i][j]\n",
    "            return ans\n",
    "\n",
    "        R, C = len(mat), len(mat[0])\n",
    "        res = [[0] * C for r in range(R)]\n",
    "        for r  in range(R):\n",
    "            for c in range(C):\n",
    "                res[r][c] = check(r, c)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "\n",
    "        answer = []\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        for r in range(m):\n",
    "            tmp = []\n",
    "            for c in range(n):\n",
    "                upper_r = min(m, r+k+1)\n",
    "                lower_r = max(0, r-k)\n",
    "                upper_c = min(n, c+k+1)\n",
    "                lower_c = max(0, c-k)\n",
    "                summ = 0\n",
    "                for i in range(lower_r, upper_r):\n",
    "                    for j in range(lower_c, upper_c):\n",
    "                        summ += mat[i][j]\n",
    "                tmp.append(summ)\n",
    "\n",
    "            answer.append(tmp)\n",
    "\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        rows, cols = mat.__len__(), mat[0].__len__()\n",
    "        def call(mat, rows, cols, ci, cj, k):\n",
    "            ans = 0\n",
    "            for i in range(max(0, ci-k), min(ci+k+1, rows)):\n",
    "                for j in range(max(0, cj-k), min(cj+k+1, cols)):\n",
    "                    ans += mat[i][j]\n",
    "            return ans\n",
    "        res = []\n",
    "        for _ in range(rows):\n",
    "            res.append([0] * cols)\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                res[i][j] = call(mat, rows, cols, i, j, k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "\n",
    "        answer = []\n",
    "        m, n = len(mat), len(mat[0])\n",
    "\n",
    "        for r in range(len(mat)):\n",
    "            tmp = []\n",
    "            for c in range(len(mat[0])):\n",
    "                upper_r = min(m, r+k+1)\n",
    "                lower_r = max(0, r-k)\n",
    "                upper_c = min(n, c+k+1)\n",
    "                lower_c = max(0, c-k)\n",
    "                summ = 0\n",
    "                for i in range(lower_r, upper_r):\n",
    "                    for j in range(lower_c, upper_c):\n",
    "                        summ += mat[i][j]\n",
    "                tmp.append(summ)\n",
    "\n",
    "            answer.append(tmp)\n",
    "\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        prefix = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                prefix[i][j] = prefix[i-1][j] + \\\n",
    "                               prefix[i][j-1] + \\\n",
    "                               mat[i-1][j-1] - \\\n",
    "                               prefix[i-1][j-1]\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                x1 = max(0, row-k)\n",
    "                y1 = max(0, col-k)\n",
    "\n",
    "                x2 = min(row+k, m-1)\n",
    "                y2 = min(col+k, n-1)\n",
    "\n",
    "                res[row][col] = prefix[x2+1][y2+1] - \\\n",
    "                                prefix[x1][y2+1] - \\\n",
    "                                prefix[x2+1][y1] + \\\n",
    "                                prefix[x1][y1]\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        sum_j = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(min(k+1, n)):\n",
    "                sum_j[i][0] += mat[i][j]\n",
    "            for j in range(1, n):\n",
    "                sum_j[i][j] = sum_j[i][j-1]\n",
    "                if j > k:\n",
    "                    sum_j[i][j] -= mat[i][j-k-1]\n",
    "                if j < n-k:\n",
    "                    sum_j[i][j] += mat[i][j+k]\n",
    "        answer = [[0]*n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            for i in range(min(k+1, m)):\n",
    "                answer[0][j] += sum_j[i][j]\n",
    "            for i in range(1, m):\n",
    "                answer[i][j] = answer[i-1][j]\n",
    "                if i > k:\n",
    "                    answer[i][j] -= sum_j[i-k-1][j]\n",
    "                if i < m-k:\n",
    "                    answer[i][j] += sum_j[i+k][j]\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        n,m=len(mat),len(mat[0])\n",
    "        prefix=[[0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                prefix[i+1][j+1]=prefix[i+1][j]+prefix[i][j+1]-prefix[i][j]+mat[i][j]\n",
    "        res=[[0]*(m) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                row1,row2=max(0,i-k),min(n-1,i+k)\n",
    "                col1,col2=max(0,j-k),min(m-1,j+k)\n",
    "                res[i][j]=prefix[row2+1][col2+1]-prefix[row2+1][col1]-prefix[row1][col2+1]+prefix[row1][col1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + k + 1, j + k + 1) - get(i - k, j + k + 1) - get(i + k + 1, j - k) + get(i - k, j - k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\tdef matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "\n",
    "\t\ts = [[y for y in x] for x in mat]\n",
    "\n",
    "\t\tfor i in range(len(mat)):\n",
    "\t\t\tfor j in range(len(mat[0])):\n",
    "\t\t\t\tif i > 0:\n",
    "\t\t\t\t\tif j > 0:\n",
    "\t\t\t\t\t\ts[i][j] += s[i - 1][j] + s[i][j-1]-s[i-1][j-1]\n",
    "\t\t\t\t\telse:\n",
    "\t\t\t\t\t\ts[i][j] += s[i - 1][j]\n",
    "\t\t\t\telse:\n",
    "\t\t\t\t\tif j > 0:\n",
    "\t\t\t\t\t\ts[i][j] += s[i][j - 1]\n",
    "\n",
    "\t\tr = [[0 for y in x] for x in mat]\n",
    "\t\tfor i in range(len(mat)):\n",
    "\t\t\tfor j in range(len(mat[0])):\n",
    "\t\t\t\tr1 = max(0, i-k)\n",
    "\t\t\t\tr2 = min(len(mat)-1, i+k)\n",
    "\t\t\t\tc1 = max(0, j-k)\n",
    "\t\t\t\tc2 = min(len(mat[0])-1, j+k)\n",
    "\t\t\t\tr[i][j] = self.getBlock(s, r1, c1, r2, c2)\n",
    "\t\treturn r\n",
    "\n",
    "\n",
    "\tdef getBlock(self, s, r1, c1, r2, c2):\n",
    "\t\tif r1 > 0:\n",
    "\t\t\tif c1 > 0:\n",
    "\t\t\t\treturn s[r2][c2] + s[r1-1][c1-1] - s[r2][c1-1] - s[r1-1][c2]\n",
    "\t\t\telse:\n",
    "\t\t\t\treturn s[r2][c2] - s[r1-1][c2]\n",
    "\t\telif c1 > 0:\n",
    "\t\t\treturn s[r2][c2] - s[r2][c1-1]\n",
    "\t\treturn s[r2][c2]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\r\n",
    "        m, n = len(mat), len(mat[0])\r\n",
    "        answer = [[0] * n for _ in range(m)]\r\n",
    "        for r in range(m):\r\n",
    "            for c in range(n):\r\n",
    "                if r == 0 and c == 0:\r\n",
    "                    answer[r][c] = sum(mat[i][j] for i in range(k+1) if i < m \\\r\n",
    "                                                 for j in range(k+1) if j < n)\r\n",
    "                elif c == 0:\r\n",
    "                    answer[r][c] = answer[r - 1][c] - \\\r\n",
    "                        (sum(mat[r - 1 - k][j] for j in range(k + 1) if j < n) if r - 1 - k >= 0 else 0) + \\\r\n",
    "                        (sum(mat[r + k][j] for j in range(k + 1) if j < n) if r + k < m else 0)\r\n",
    "                else:\r\n",
    "                    answer[r][c] = answer[r][c - 1] - \\\r\n",
    "                        (sum(mat[i][c - 1 - k] for i in range(r - k, r + k + 1) if 0 <= i < m) if c - 1 - k >= 0 else 0) + \\\r\n",
    "                        (sum(mat[i][c + k] for i in range(r - k, r + k + 1) if 0 <= i < m) if c + k < n else 0)\r\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "二维前缀和+容斥原理\n",
    "1. 计算A[i][j]表示从左上角mat[0][0]到右下角mat[i][j]组成的矩阵的元素和\n",
    "2. answer[i][j] = mat[i-k][j-k]为左上角，mat[i+k][j+k]为右下角组成的矩阵的元素和 = A[i+k][j+k] - A[i+k][j-k-1] - A[i-k-1][j+k] + A[i-k-1][j-k-1]\n",
    "\"\"\"\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        n,d = len(mat), len(mat[0])\n",
    "        pre_sum = deepcopy(mat)\n",
    "        ret = [[0] * d for _ in range(n)]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            pre_sum[i][0] += pre_sum[i-1][0]\n",
    "        for j in range(1, d):\n",
    "            pre_sum[0][j] += pre_sum[0][j-1]\n",
    "        \n",
    "        for i in range(1, n):\n",
    "            for j in range(1, d):\n",
    "                pre_sum[i][j] = pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1] + mat[i][j]\n",
    "        # print(pre_sum)\n",
    "        for i in range(n):\n",
    "            for j in range(d):\n",
    "                begin = max(0, i-k), max(0, j-k)\n",
    "                end = min(n-1, i+k), min(d-1, j+k)\n",
    "                # print(f\"i: {i}, j: {j}\")\n",
    "                # print(f\"begin: {begin}\")\n",
    "                # print(f\"end: {end}\")\n",
    "                a = pre_sum[end[0]][end[1]]\n",
    "                b = pre_sum[end[0]][begin[1]-1] if begin[1]-1 >= 0 else 0\n",
    "                c = pre_sum[begin[0]-1][end[1]] if begin[0]-1 >= 0 else 0\n",
    "                e = pre_sum[begin[0]-1][begin[1]-1] if begin[0]-1 >= 0 and begin[1]-1 >= 0 else 0\n",
    "                ret[i][j] = a - b - c + e\n",
    "        return ret\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        res = [[0] * (n) for _ in range(m)]\n",
    "        obj = NumMatrix(mat)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # 左上角坐标\n",
    "                x1 = max(i-k, 0)\n",
    "                y1 = max(j-k, 0)\n",
    "\n",
    "                # 右下角坐标\n",
    "                x2 = min(i+k, m-1)\n",
    "                y2 = min(j+k, n-1)\n",
    "\n",
    "                res[i][j] = obj.sumRegion(x1, y1, x2, y2)\n",
    "                \n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "class NumMatrix:\n",
    "\n",
    "    def __init__(self, matrix: List[List[int]]):\n",
    "        # preSum[i][j] 记录matrix[0..i-1][0..j-1]的前缀和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        self.preSum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(0, m):\n",
    "            for j in range(0, n):\n",
    "                self.preSum[i+1][j+1] = self.preSum[i+1][j] + self.preSum[i][j+1] - self.preSum[i][j] + matrix[i][j]\n",
    "\n",
    "\n",
    "    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:\n",
    "        \n",
    "        return self.preSum[row2+1][col2+1] + self.preSum[row1][col1] - self.preSum[row1][col2+1] -self.preSum[row2+1][col1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        p = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                p[i][j] = p[i-1][j] + p[i][j-1] - p[i-1][j-1] + mat[i-1][j-1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return p[x][y]\n",
    "        \n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j] = get(i+k+1, j+k+1) - get(i-k, j+k+1) - get(i+k+1, j-k) + get(i-k, j-k)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        summatrix = [[0] * (n + 1) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if j == 0:\n",
    "                    summatrix[i][j] = mat[i][j]\n",
    "                else:\n",
    "                    summatrix[i][j] = summatrix[i][j-1] + mat[i][j]\n",
    "        \n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                r1, r2, c1, c2 = 0, 0, 0, 0\n",
    "\n",
    "                r1 = 0 if i - k < 0 else i - k\n",
    "                r2 = m - 1 if i + k > m -1 else i + k\n",
    "                c1 = 0 if j - k < 0 else j - k\n",
    "                c2 = n - 1 if j + k > n-1 else j + k\n",
    "                for r in range(r1, r2 + 1):\n",
    "                    res[i][j] += summatrix[r][c2] - summatrix[r][c1 - 1]\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        nums=[[0]*(n+1) for _ in range(m+1)]\n",
    "        result=[[0]*(n) for _ in range(m)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                nums[i][j]=mat[i-1][j-1]+nums[i-1][j]+nums[i][j-1]-nums[i-1][j-1]\n",
    "        \n",
    "        for row in range(m):\n",
    "            for cloumn in range(n):\n",
    "                cur_row1=row-k\n",
    "                cur_cloumn1=cloumn-k\n",
    "                cur_row2=row+k\n",
    "                cur_cloumn2=cloumn+k\n",
    "                if cur_row1<0:\n",
    "                    cur_row1=0\n",
    "                if cur_cloumn1<0:\n",
    "                    cur_cloumn1=0\n",
    "                \n",
    "                if cur_row2>m-1:\n",
    "                    cur_row2=m-1\n",
    "                if cur_cloumn2>n-1:\n",
    "                    cur_cloumn2=n-1\n",
    "\n",
    "                result[row][cloumn]=nums[cur_row2+1][cur_cloumn2+1]-nums[cur_row1][cur_cloumn2+1]-nums[cur_row2+1][cur_cloumn1]+nums[cur_row1][cur_cloumn1]\n",
    "        \n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def conv(mat_):\n",
    "            row = len(mat_)\n",
    "            col = len(mat_[0])\n",
    "            ans = [[] for _ in range(row)]\n",
    "            for i, l in enumerate(mat_):\n",
    "                sm = sum(l[:k])\n",
    "                for j in range(col):\n",
    "                    if j + k < col:\n",
    "                        sm += l[j + k]\n",
    "                    if j - k > 0:\n",
    "                        sm -= l[j - k - 1]\n",
    "                    ans[i].append(sm)\n",
    "            return ans\n",
    "        \n",
    "        return [*zip(*conv([*zip(*conv(mat))]))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        sum_j = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(min(k+1, n)):\n",
    "                sum_j[i][0] += mat[i][j]\n",
    "            for j in range(1, n):\n",
    "                sum_j[i][j] = sum_j[i][j-1]\n",
    "                if j > k:\n",
    "                    sum_j[i][j] -= mat[i][j-k-1]\n",
    "                if j < n-k:\n",
    "                    sum_j[i][j] += mat[i][j+k]\n",
    "        answer = [[0]*n for _ in range(m)]\n",
    "        for j in range(n):\n",
    "            for i in range(min(k+1, m)):\n",
    "                answer[0][j] += sum_j[i][j]\n",
    "            for i in range(1, m):\n",
    "                answer[i][j] = answer[i-1][j]\n",
    "                if i > k:\n",
    "                    answer[i][j] -= sum_j[i-k-1][j]\n",
    "                if i < m-k:\n",
    "                    answer[i][j] += sum_j[i+k][j]\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        # 二维前缀和\n",
    "        # 构建二维前缀和矩阵\n",
    "        # dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i][j]\n",
    "        preMat = preMatrix(mat)\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x1 = max(0,i-k)\n",
    "                y1 = max(0,j-k)\n",
    "                x2 = min(m-1,i+k)\n",
    "                y2 = min(n-1,j+k)\n",
    "                res[i][j] = preMat.sumRegion(x1,y1,x2,y2)\n",
    "        return res\n",
    "class preMatrix:\n",
    "    def __init__(self,mat):\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        if n == 0 or m == 0:\n",
    "            return\n",
    "        self.dp = [[0 for _ in range(n+1)] for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                self.dp[i][j] = self.dp[i-1][j] + self.dp[i][j-1] - self.dp[i-1][j-1] + mat[i-1][j-1]\n",
    "    def sumRegion(self,x1,y1,x2,y2):\n",
    "        return self.dp[x2+1][y2+1] - self.dp[x1][y2+1] - self.dp[x2+1][y1] + self.dp[x1][y1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "\n",
    "        preSum = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        for i in range(m):\n",
    "            rows = []\n",
    "            r0 = max(i - k, 0)\n",
    "            r1 = min(i + k, m - 1)\n",
    "            for j in range(n):\n",
    "                c0 = max(j - k, 0)\n",
    "                c1 = min(j + k, n - 1)\n",
    "                cur = preSum[r1 + 1][c1 + 1] \\\n",
    "                        - preSum[r1 + 1][c0] \\\n",
    "                        - preSum[r0][c1 + 1] \\\n",
    "                        + preSum[r0][c0]\n",
    "                rows.append(cur)\n",
    "            ans.append(rows)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def conv(mat_):\n",
    "            row = len(mat_)\n",
    "            col = len(mat_[0])\n",
    "            ans = [[] for _ in range(row)]\n",
    "            for i, l in enumerate(mat_):\n",
    "                sm = sum(l[:k])\n",
    "                for j in range(col):\n",
    "                    if j + k < col:\n",
    "                        sm += l[j + k]\n",
    "                    if j - k > 0:\n",
    "                        sm -= l[j - k - 1]\n",
    "                    ans[i].append(sm)\n",
    "            return [*zip(*ans)]\n",
    "        \n",
    "        return conv(conv(mat))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pre_s = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre_s[i][j] = pre_s[i-1][j] + pre_s[i][j - 1] - pre_s[i-1][j-1] + mat[i-1][j-1]\n",
    "        # print(pre_s)\n",
    "        def get(x, y):\n",
    "            x = max(min(x,m), 0)\n",
    "            y = max(min(y,n), 0)\n",
    "            return pre_s[x][y]\n",
    "        \n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i+k+1, j + k + 1) - get(i-k, j + k+1) - get(i+k+1, j -k) + get(i-k, j-k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def rcnum(self, x, y):\n",
    "        row1 = 0 if x-self.k < 0 else x-self.k\n",
    "        row2 = self.row_num-1 if x + self.k > self.row_num-1 else x + self.k\n",
    "        col1 = 0 if y-self.k < 0 else y-self.k\n",
    "        col2 = self.col_num-1 if y + self.k > self.col_num-1 else y + self.k\n",
    "        return row1, col1, row2, col2\n",
    "\n",
    "\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        self.k = k\n",
    "        self.row_num = len(mat)\n",
    "        self.col_num = len(mat[0])\n",
    "        self.presum = [[0 for _ in range(self.col_num +1)] for _ in range(self.row_num +1)]\n",
    "        print(self.presum)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, num in enumerate(row):\n",
    "                self.presum[i+1][j+1] = self.presum[i][j+1] + self.presum[i+1][j] - self.presum[i][j] + num\n",
    "        self.result = [[0 for _ in range(self.col_num)] for _ in range(self.row_num)]\n",
    "        for i in range(self.row_num):\n",
    "            for j in range(self.col_num):\n",
    "                row1, col1, row2, col2 = self.rcnum(i, j)\n",
    "                self.result[i][j] = self.presum[row2+1][col2+1] - self.presum[row1][col2+1] - self.presum[row2+1][col1] + self.presum[row1][col1]\n",
    "        return self.result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pre_s = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre_s[i][j] = pre_s[i-1][j] + pre_s[i][j - 1] - pre_s[i-1][j-1] + mat[i-1][j-1]\n",
    "        # print(pre_s)\n",
    "        def get(x, y):\n",
    "            x = max(min(x,m), 0)\n",
    "            y = max(min(y,n), 0)\n",
    "            return pre_s[x][y]\n",
    "        \n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i+k+1, j + k + 1) - get(i-k, j + k+1) - get(i+k+1, j -k) + get(i-k, j-k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + k + 1, j + k + 1) - get(i - k, j + k + 1) - get(i + k + 1, j - k) + get(i - k, j - k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        h = len(mat)\n",
    "        if h > 0:\n",
    "            w = len(mat[0])\n",
    "            if w == 0:\n",
    "                return [[]]\n",
    "        else:\n",
    "            return [[]]\n",
    "\n",
    "        presum = [[0]* (w+1) for _ in range(h+1)]\n",
    "        for i in range(1, h+1):\n",
    "            for j in range(1, w+1):\n",
    "                presum[i][j] = presum[i-1][j] + presum[i][j-1] + mat[i-1][j-1] - presum[i-1][j-1]\n",
    "\n",
    "        answer = [[0]*w for _ in range(h)]\n",
    "\n",
    "        def get(x, y):\n",
    "            x = max(min(x, h), 0)\n",
    "            y = max(min(y, w), 0)\n",
    "            return presum[x][y]\n",
    "\n",
    "        for i in range(h):\n",
    "            for j in range(w):\n",
    "                answer[i][j] = get(i+k+1, j+k+1) + get(i-k, j-k) - get(i-k, j+k+1) - get(i+k+1, j-k)\n",
    "\n",
    "        # for c in range(h):\n",
    "        #     for r in range(w):\n",
    "        #         left_x = max(0, c-k)\n",
    "        #         right_x = min(c+k, w-1)\n",
    "        #         top_y = max(0, r-k)\n",
    "        #         bot_y = min(r+k, h-1)\n",
    "        #         answer[c][r] = presum[bot_y+1][right_x+1] + presum[top_y][left_x] - presum[bot_y+1][left_x] - presum[top_y][right_x+1]\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        mat_sum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                mat_sum[i][j] = mat_sum[i-1][j] + mat_sum[i][j-1] - mat_sum[i-1][j-1] + mat[i-1][j-1]\n",
    "\n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return mat_sum[x][y]\n",
    "\n",
    "        answer = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                answer[i][j] = get(i+k+1, j+k+1) - get(i-k, j+k+1) - get(i+k+1, j-k) + get(i-k, j-k)\n",
    "        \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + k + 1, j + k + 1) - get(i - k, j + k + 1) - get(i + k + 1, j - k) + get(i - k, j - k)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def conv(mat_):\n",
    "            row = len(mat_)\n",
    "            col = len(mat_[0])\n",
    "            ans = [[] for _ in range(row)]\n",
    "            for i, l in enumerate(mat_):\n",
    "                sm = sum(l[:k])\n",
    "                for j in range(col):\n",
    "                    if j + k < col:\n",
    "                        sm += l[j + k]\n",
    "                    if j - k > 0:\n",
    "                        sm -= l[j - k - 1]\n",
    "                    ans[i].append(sm)\n",
    "            return [*zip(*ans)]\n",
    "        \n",
    "        return conv(conv(mat))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        preSum = [ [0]*(m+1) for _ in range(n+1)]\n",
    "        for i in range(1, n+1):\n",
    "            for j in range(1, m+1):\n",
    "                preSum[i][j] = preSum[i][j-1] + preSum[i-1][j] - preSum[i-1][j-1] + mat[i-1][j-1]\n",
    "        \n",
    "        res = [ [0]*(m) for _ in range(n)]\n",
    "        for i in range(0, n):\n",
    "            for j in range(0, m):\n",
    "                x1 = i-k if i-k >=0 else 0\n",
    "                x2 = i+k if i+k <= n-1 else n-1\n",
    "                y1 = j-k if j-k >=0 else 0\n",
    "                y2 = j+k if j+k <= m-1 else m-1\n",
    "                res[i][j] = preSum[x2+1][y2+1] - preSum[x1][y2+1] - preSum[x2+1][y1] + preSum[x1][y1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sums = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                sums[i][j] = sum(mat[i][max(j-K, 0):min(j+K+1, n)])\n",
    "        res = [[0]*n for _ in range(m)]\n",
    "        for i in range(0, m):\n",
    "            for j in range(n):\n",
    "                res[i][j] = sum([sums[p][j] for p in range(max(i-K, 0), min(i+K+1, m))])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        prefix = pre(mat)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                col1,col2,row1,row2 = max(i-k,0),min(i+k,m-1),max(j-k,0),min(j+k,n-1)\n",
    "                mat[i][j] = prefix.query(col1,row1,col2,row2)\n",
    "        return mat\n",
    "\n",
    "\n",
    "class pre:\n",
    "    def __init__(self,mat):\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        self.matrix = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.matrix[i+1][j+1] = self.matrix[i+1][j]+self.matrix[i][j+1]-self.matrix[i][j]+mat[i][j]\n",
    "    def query(self,col1,rol1,col2,rol2):\n",
    "        return self.matrix[col2+1][rol2+1]-self.matrix[col2+1][rol1]-self.matrix[col1][rol2+1]+self.matrix[col1][rol1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class MatrixBlockSum:\n",
    "        \n",
    "    def __init__(self, mat):\n",
    "        rows, cols = len(mat), len(mat[0])\n",
    "        self.pre_sum = [[0 for _ in range(cols + 1)] for _ in range(rows + 1)]\n",
    "        for i in range(1, rows + 1):\n",
    "            for j in range(1, cols + 1):\n",
    "                self.pre_sum[i][j] = self.pre_sum[i - 1][j] + self.pre_sum[i][j - 1] + mat[i - 1][j - 1] - self.pre_sum[i - 1][j - 1] \n",
    "\n",
    "        # mat 左上(x1, y1) -> 右下(x2, y2)的区域和\n",
    "    def get_region_sum(self, x1, y1, x2, y2):\n",
    "        return self.pre_sum[x2 + 1][y2 + 1] - self.pre_sum[x1][y2 + 1] - self.pre_sum[x2 + 1][y1] + self.pre_sum[x1][y1]\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        \n",
    "        rows, cols = len(mat), len(mat[0])\n",
    "        res = [[0 for _ in range(cols)] for _ in range(rows)]\n",
    "\n",
    "        mat_block = MatrixBlockSum(mat)\n",
    "\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                x1 = max(i - k, 0)\n",
    "                y1 = max(j - k, 0)\n",
    "                x2 = min(i + k, rows - 1)\n",
    "                y2 = min(j + k, cols - 1)\n",
    "                res[i][j] = mat_block.get_region_sum(x1, y1, x2, y2)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        prefix = pre(mat)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                col1,col2,row1,row2 = max(i-k,0),min(i+k,m-1),max(j-k,0),min(j+k,n-1)\n",
    "                mat[i][j] = prefix.query(col1,row1,col2,row2)\n",
    "        return mat\n",
    "\n",
    "\n",
    "class pre:\n",
    "    def __init__(self,mat):\n",
    "        m,n = len(mat),len(mat[0])\n",
    "        self.matrix = [[0]*(n+1) for _ in range(m+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                self.matrix[i+1][j+1] = self.matrix[i+1][j]+self.matrix[i][j+1]-self.matrix[i][j]+mat[i][j]\n",
    "    def query(self,col1,rol1,col2,rol2):\n",
    "        return self.matrix[col2+1][rol2+1]-self.matrix[col2+1][rol1]-self.matrix[col1][rol2+1]+self.matrix[col1][rol1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        \n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "\n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def matrixBlockSum(self, mat: List[List[int]], K: int) -> List[List[int]]:\r\n",
    "        m, n = len(mat), len(mat[0])\r\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\r\n",
    "        for i in range(1, m + 1):\r\n",
    "            for j in range(1, n + 1):\r\n",
    "                P[i][j] = P[i - 1][j] + P[i][j - 1] - P[i - 1][j - 1] + mat[i - 1][j - 1]\r\n",
    "        \r\n",
    "        def get(x, y):\r\n",
    "            x = max(min(x, m), 0)\r\n",
    "            y = max(min(y, n), 0)\r\n",
    "            return P[x][y]\r\n",
    "\r\n",
    "        ans = [[0] * n for _ in range(m)]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                ans[i][j] = get(i + K + 1, j + K + 1) - get(i - K, j + K + 1) - get(i + K + 1, j - K) + get(i - K, j - K);\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        P = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(1, m+1):\n",
    "            for j in range(1, n+1):\n",
    "                P[i][j] = P[i-1][j] + P[i][j-1]  - P[i-1][j-1] + mat[i-1][j-1]\n",
    "        def get(x, y):\n",
    "            x = max(min(x, m), 0)\n",
    "            y = max(min(y, n), 0)\n",
    "            return P[x][y]\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res[i][j] = get(i + k + 1, j + k + 1) - get(i - k, j + k + 1) - get(i + k + 1, j - k) + get(i - k, j - k)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        col = len(mat[0])\n",
    "\n",
    "        # 行滑动窗口\n",
    "        row_sum = [[] for _ in range(row)]\n",
    "        for i, l in enumerate(mat):\n",
    "            sm = sum(l[:k])\n",
    "            for j in range(col):\n",
    "                if j + k < col:\n",
    "                    sm += l[j + k]\n",
    "                if j - k > 0:\n",
    "                    sm -= l[j - k - 1]\n",
    "                row_sum[i].append(sm)\n",
    "        \n",
    "        # 列滑动窗口\n",
    "        ans = [[] for _ in range(row)]\n",
    "        for i, l in enumerate(zip(*row_sum)):\n",
    "            sm = sum(l[:k])\n",
    "            for j in range(row):\n",
    "                if j + k < row:\n",
    "                    sm += l[j + k]\n",
    "                if j - k > 0:\n",
    "                    sm -= l[j - k - 1]\n",
    "                ans[j].append(sm)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        # 二维前缀和\n",
    "        row,col=len(mat),len(mat[0])\n",
    "        preSum=[[0 for _ in range(col+10)] for _ in range(row+10)]\n",
    "\n",
    "        # 预处理\n",
    "        for i in range(1,row+1):\n",
    "            for j in range(1,col+1):\n",
    "                preSum[i][j]=preSum[i-1][j]+preSum[i][j-1]-preSum[i-1][j-1]+mat[i-1][j-1]\n",
    "        \n",
    "        # 计算区间和\n",
    "        def sumRange(x1,y1,x2,y2):\n",
    "            nonlocal preSum\n",
    "            return preSum[x2+1][y2+1]-preSum[x1][y2+1]-preSum [x2+1][y1]+preSum[x1][y1]\n",
    "        \n",
    "        answer=[[0 for _ in range(col)] for _ in range(row)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                x1,x2=max(i-k,0),min(i+k,row-1)\n",
    "                y1,y2=max(j-k,0),min(j+k,col-1)\n",
    "                answer[i][j]=sumRange(x1,y1,x2,y2)\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sub = []\n",
    "        for i in range(m):\n",
    "            subsub = [0]\n",
    "            for num in mat[i]:\n",
    "                subsub.append(num + subsub[-1])\n",
    "            sub.append(subsub)\n",
    "        print(sub)\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            for j in range(n):\n",
    "                l, r = max(0, j - k), min(n - 1, j + k)\n",
    "                start, end = max(0, i - k), min(m - 1, i + k)\n",
    "                s = 0\n",
    "                for x in range(start, end + 1):\n",
    "                    s += sub[x][r + 1] - sub[x][l]\n",
    "                tmp.append(s)\n",
    "            res.append(tmp)\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                dp[i][j] = dp[i][j - 1] + dp[i - 1][j] - dp[i - 1][j - 1] + mat[i - 1][j - 1]\n",
    "        ans = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                bottom, up = max(i - k, 0) - 1, min(i + k, m - 1)\n",
    "                left, right = max(j - k, 0) - 1, min(j + k, n - 1)\n",
    "                ans[i][j] = dp[up + 1][right + 1] + dp[bottom + 1][left + 1] - dp[up + 1][left + 1] - dp[bottom + 1][right + 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        rowSum = [[0] * (m + 1) for _ in mat]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                rowSum[i][j + 1] += mat[i][j] + rowSum[i][j]\n",
    "        ans = [[0] * m for _ in mat]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                print(max(0, i - k), min(n, i + k))\n",
    "                for q in range(max(0, i - k), min(n, i + k + 1)):\n",
    "                    ans[i][j] += rowSum[q][min(m, j + k + 1)] - rowSum[q][max(0, j - k)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        presum = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                presum[i][j] = presum[i-1][j] + presum[i][j-1] + mat[i-1][j-1] - presum[i-1][j-1]\n",
    "        \n",
    "\n",
    "        res = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x1 = max(i - k,0)\n",
    "                y1 = max(j - k,0)\n",
    "                x2 = min(i + k + 1,m)\n",
    "                y2 = min(j + k + 1,n)\n",
    "\n",
    "                res[i][j] = presum[x2][y2] - presum[x1][y2] - presum[x2][y1] + presum[x1][y1]\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        def conv(mat_):\n",
    "            row = len(mat_)\n",
    "            col = len(mat_[0])\n",
    "            ans = [[] for _ in range(row)]\n",
    "            for i, l in enumerate(mat_):\n",
    "                sm = sum(l[:k])\n",
    "                for j in range(col):\n",
    "                    if j + k < col:\n",
    "                        sm += l[j + k]\n",
    "                    if j - k > 0:\n",
    "                        sm -= l[j - k - 1]\n",
    "                    ans[i].append(sm)\n",
    "            return ans\n",
    "        \n",
    "        return [*zip(*conv([*zip(*conv(mat))]))]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sub = []\n",
    "        for i in range(m):\n",
    "            subsub = [0]\n",
    "            for num in mat[i]:\n",
    "                subsub.append(num + subsub[-1])\n",
    "            sub.append(subsub)\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            for j in range(n):\n",
    "                l, r = max(0, j - k), min(n - 1, j + k)\n",
    "                start, end = max(0, i - k), min(m - 1, i + k)\n",
    "                s = 0\n",
    "                for x in range(start, end + 1):\n",
    "                    s += sub[x][r + 1] - sub[x][l]\n",
    "                tmp.append(s)\n",
    "            res.append(tmp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pre_s = [[0] * (n+1) for _ in range(m+1)]\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                pre_s[i][j] = pre_s[i-1][j] + pre_s[i][j - 1] - pre_s[i-1][j-1] + mat[i-1][j-1]\n",
    "        print(pre_s)\n",
    "        def get(x, y):\n",
    "            x = max(min(x,m), 0)\n",
    "            y = max(min(y,n), 0)\n",
    "            return pre_s[x][y]\n",
    "        \n",
    "        ans = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans[i][j] = get(i+k+1, j + k + 1) - get(i-k, j + k+1) - get(i+k+1, j -k) + get(i-k, j-k)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m , n = len(mat) , len(mat[0])\n",
    "        row_sum = [[0]*(n+1) for i in range(m+1)]\n",
    "        for i in range(1,m+1):\n",
    "            sums = 0\n",
    "            for j in range(1,n+1):\n",
    "                sums += mat[i-1][j-1]\n",
    "                row_sum[i][j] = sums\n",
    "\n",
    "        mat_sum = [[0]*(n+1) for i in range(m+1)]\n",
    "        sums = 0\n",
    "        for i in range(1,m+1):\n",
    "            for j in range(1,n+1):\n",
    "                mat_sum[i][j] = row_sum[i][j]+mat_sum[i-1][j]\n",
    "        \n",
    "        ans = mat\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                r , d = j+k , i+k\n",
    "                left , up , c = 0 , 0 , 0\n",
    "                if d >= m: d = m-1\n",
    "                if r >= n: r = n-1\n",
    "                if i - k > 0: up = mat_sum[i-k][r+1]\n",
    "                if j - k > 0: left = mat_sum[d+1][j-k]\n",
    "                if i - k > 0 and j - k > 0: c = mat_sum[i-k][j-k]\n",
    "                ans[i][j] = mat_sum[d+1][r+1]-left-up+c\n",
    "        return ans\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        row = len(mat)\n",
    "        col = len(mat[0])\n",
    "        sum_list = [[0]* (col+1) for _ in range(row+1)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                sum_list[i+1][j+1] = sum_list[i][j+1] + sum_list[i+1][j] -sum_list[i][j]+mat[i][j]\n",
    "        sum_out = [[0]* col for _ in range(row)]\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                x1 = max(0,i-k)\n",
    "                x2 = min(row-1, i+k)\n",
    "                y1 = max(0,j-k)\n",
    "                y2 = min(col-1, j+k)\n",
    "                print(x1,x2,y1,y2)\n",
    "                sum_out[i][j] = sum_list[x2+1][y2+1] - sum_list[x1][y2+1] -sum_list[x2+1][y1] + sum_list[x1][y1]\n",
    "        return sum_out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        sub = []\n",
    "        for i in range(m):\n",
    "            subsub = [0]\n",
    "            for num in mat[i]:\n",
    "                subsub.append(num + subsub[-1])\n",
    "            sub.append(subsub)\n",
    "        print(sub)\n",
    "        res = []\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            for j in range(n):\n",
    "                l, r = max(0, j - k), min(n - 1, j + k)\n",
    "                start, end = max(0, i - k), min(m - 1, i + k)\n",
    "                s = 0\n",
    "                for x in range(start, end + 1):\n",
    "                    s += sub[x][r + 1] - sub[x][l]\n",
    "                tmp.append(s)\n",
    "            res.append(tmp)\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        pre=[[0] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in mat[i]:\n",
    "                pre[i].append(pre[i][-1]+j)\n",
    "        print(pre)\n",
    "        res=[[0 for _ in range(n)] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                l=max(j-k,0)\n",
    "                r=min(j+k+1,n)\n",
    "                u=max(i-k,0)\n",
    "                d=min(i+k+1,m)\n",
    "                tmp=0\n",
    "                for t in range(u,d):\n",
    "                    tmp+=pre[t][r]-pre[t][l]\n",
    "                res[i][j]=tmp\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\r\n",
    "        m, n = len(mat), len(mat[0])\r\n",
    "        answer = [[0] * n for _ in range(m)]\r\n",
    "        pre_sum = [[0] * (n + 1) for _ in range(m + 1)]\r\n",
    "        for i in range(1, m + 1):\r\n",
    "            for j in range(1, n + 1):\r\n",
    "                pre_sum[i][j] = pre_sum[i - 1][j] + pre_sum[i][j - 1] - pre_sum[i - 1][j - 1] + mat[i - 1][j - 1]\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                x1, y1, x2, y2 = max(0, i - k), max(0, j - k), min(m - 1, i + k), min(n - 1, j + k)\r\n",
    "                answer[i][j] = pre_sum[x2 + 1][y2 + 1] - pre_sum[x2 + 1][y1] - pre_sum[x1][y2 + 1] + pre_sum[x1][y1]\r\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def matrixBlockSum(self, mat: List[List[int]], k: int) -> List[List[int]]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "\n",
    "        mat_cumsum = [[0]*(len(mat[0])+1) for i in range(len(mat)+1)]\n",
    "        for i in range(1,len(mat)+1):\n",
    "            for j in range(1,len(mat[0])+1):\n",
    "                mat_cumsum[i][j] = mat[i-1][j-1] + mat_cumsum[i-1][j] + mat_cumsum[i][j-1] - mat_cumsum[i-1][j-1]\n",
    "        def returnindex(i,j,k,m,n):\n",
    "            # m: length of rows\n",
    "            # n: length of the cols\n",
    "            # righ lower\n",
    "            row1 = min(m,i+k)\n",
    "            col1 = min(n,j+k)\n",
    "            #left upper\n",
    "            row2 = max(0,i-k)\n",
    "            col2 = max(0,j-k)\n",
    "            return row1, col1, row2, col2\n",
    "\n",
    "        result = [[0]*(n) for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                row1 = returnindex(i,j,k,m,n)[0]\n",
    "                col1 = returnindex(i,j,k,m,n)[1]\n",
    "                row2 = returnindex(i,j,k,m,n)[2]\n",
    "                col2 = returnindex(i,j,k,m,n)[3]\n",
    "                print( returnindex(i,j,k,m,n))\n",
    "                print(m+1,n+1)\n",
    "                pre = mat_cumsum\n",
    "\n",
    "                result[i][j] =  pre[min(row1+1,m)][min(col1+1,n)]-pre[min(row1+1,m)][col2]-pre[row2][min(col1+1,n)]+pre[row2][col2]\n",
    "\n",
    "        return result\n",
    "\n",
    "               \n",
    "                \n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
